package offer.day20;

import java.util.ArrayList;
import java.util.List;

public class No34FindPath {
    /*
     * 面试题34：二叉树中和为某一值的路径
     * 题目：输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。
     * 从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
     * 例如：输入 10->(left)5    10->(right)12 中的二叉树和整数22，
     * 		  5->(left)4      5->(right)7
     * 则打印出两条路径，第一条路径包含节点10，12   第二条路经包含10 ，5 ，7
     *
     *
     * 思路：先序遍历二叉树时，先访问根节点，然后将根节点添加到路径上，并且累加路径上的值；
     * 若该节点为叶节点，并且路径中的值加起来刚好等于那个整数，则将路径打印出来。
     * 若该节点不为叶节点，则继续访问它的子节点，然后将子节点添加到路径上，并且累加路径上的值，。。。
     * 并且在到达叶子节点后，发现路径上的值加起来并不等于那个整数，
     *    则删除当前路径上节点并（累加路径）减去当前节点的值，以确保返回父节点时路径刚好是从根节点到父节点。
     *
     * 总之，每次访问一个节点，就将其存入path，累加路径上的值，
     *     然后再判断是否为叶节点且累加和刚好相等，若相等，则表示找到了一条路径，则将其存入二维数组中
     *              若不是叶子节点，则判断左右节点是否存在，存在继续上面的步骤。。。
     *     当走到了叶子节点以后，可能找到或者没找到路径，无论找没找到都应该将path中最后的这个节点删除，然后在返回到父节点处
     * */
    public static void main(String[] args) {
        No34FindPath f = new No34FindPath();

        BinaryTreeNode root = new BinaryTreeNode(10);
        BinaryTreeNode one = new BinaryTreeNode(5);
        BinaryTreeNode two = new BinaryTreeNode(12);
        BinaryTreeNode three = new BinaryTreeNode(4);
        BinaryTreeNode four = new BinaryTreeNode(7);

        root.left = one;
        root.right = two;
        one.left = three;
        one.right = four;
        two.left = null;
        two.right = null;
        three.left = null;
        three.right = null;
        four.left = null;
        four.right = null;

        int number = 19;

        System.out.println("打印二叉树中和为"+number+"这一整数的所有路径：");
        List<ArrayList<Integer>> list =new ArrayList<>();
        List<Integer> path=new ArrayList<>();
        f.FindPath(root,number,path,list);
        for(int i = 0; i < list.size();i++) {
            System.out.println("第"+(i+1)+"条路径为："+list.get(i));
        }
    }

    private void FindPath(BinaryTreeNode root, int number,List<Integer> path,List<ArrayList<Integer>> list) {
        if(root==null) return;
        path.add(root.val);
        if(number==root.val&&root.left==null&&root.right==null){
            list.add(new ArrayList<>(path));
        }
        if(root.left!=null){
            FindPath(root.left,number-root.val,path,list);
        }
        if(root.right!=null){
            FindPath(root.right,number-root.val,path,list);
        }
        path.remove(path.size()-1);
    }
}
